package demo1;

/**
 * Description:利用链表实现一个队列--->利用单链表带两个索引
 *一个front在前面 一个rear在后面 -->我们采用尾入头出这样时间复杂度都是O(1)
 */
public class MyQueue {

    static class Node{
        //创建一个单链表，有两个索引值
        private int val;//节点的值
        private Node next;//节点next指针指向下一个节点
        public Node(int val){
            this.val = val;
        }
    }
    private Node front;//队头-->头出队
    private Node rear;//队尾--->尾入队
    private int usedSize;
    /**
     * 入队
     * @param val-
     */
    public void offer(int val){
        if(front==null){
            Node node = new Node(val);
            front = node;
            rear = node;
            this.usedSize++;
        }else {
            Node node = new Node(val);
            //尾入队
            rear.next = node;
            rear = node;
            this.usedSize++;
        }
    }

    /**
     * 获取队列大小
     */
    public int size(){
         return this.usedSize;
    }

    /**
     * 出队-->对头出队相当于头删
     */
    public int poll(){
        if(isEmpty()){
            return -1;
        }
        int ret =0;
        if(front.next==null){
            //只剩下一个节点的时候
            ret = front.val;
            front=null;
            rear=null;
            this.usedSize--;
        }else {
            ret = front.val;
            front = front.next;
            this.usedSize--;
        }
        return ret;
    }

    /**
     * 判断队列是否为空
     */
    public boolean isEmpty(){
         return this.usedSize==0;
    }

    /**
     * 获取对头元素
     */
    public int peek(){
        if(isEmpty()){
            return -1;
        }
        return front.val;
    }

}
